package main

import "fmt"

type tree struct {
	value       int
	left, right *tree
}

func main() {
	arr := []int{4, 1, 85, 96, 73, 10}
	sort(arr)
	fmt.Println(arr)
}

func sort(values []int) {
	var root *tree
	for _, v := range values {
		root = add(root, v)
	}
	appendValues(values[:0], root)
}

func appendValues(values []int, t *tree) []int {
	if t != nil {
		values = appendValues(values, t.left)
		values = append(values, t.value)
		values = appendValues(values, t.right)
	}
	return values
}

func add(root *tree, v int) *tree {
	if root == nil {
		//root = new(tree)
		//root.value = v
		root = &tree{value: v}
	} else {
		if v < root.value {
			root.left = add(root.left, v)
		} else {
			root.right = add(root.right, v)
		}
	}
	return root
}
